//
// Created by wdq on 2022/9/18.
//
#include <iostream>

using namespace std;

template<typename T>
int binarySearch(T *arr, int left, int right, T target) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

template<typename T>
int binarySearchByRecursion(T *arr, int left, int right, T target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target);
        }
    }
    return -1;

}

int main() {
    int arr[] = {2, 3, 5, 7, 8, 9};
    printf("index = %d\n", binarySearch(arr, 0, (sizeof(arr) / sizeof(int)) - 1, 3));
    printf("index = %d\n", binarySearchByRecursion(arr, 0, (sizeof(arr) / sizeof(int)) - 1, 8));
    return 0;
}
